1. Field of the Invention
This invention relates generally to cache coherence in computer systems having multiple processors with caches, and more particularly to a system and method for deleting a read-only head entry in systems supporting mixed-coherence protocol options.
2. Description of the Background Art
Multiple-processor computer systems involve various processors which at the same time may each work on a separate portion of a problem or work on a different problem. FIG. 1 shows a multi-processor system, including a plurality of Central Processing Units (CPUs) or processors 102A, 102B . . . 102N, communicating with memory 104 via interconnect 106, which could be, for example, a bus or a collection of point-to-point links. Processors 102 access data from memory 104 for a read or a write. In a read operation, processor 102 receives data from memory 104 without modifying the data, while in a write operation processor 102 modifies the data transmitted to memory 104.
Each processor 102 generally has a respective cache unit 108A, 108B, . . . 108N, which is a relatively small group of high speed memory cells dedicated to that processor. A processor 102's cache 108 is usually on the processor chip itself or may be on separate chips, but is local to processor 102. Cache 108 for each processor 102 is used to hold data that was accessed recently by that processor. Since a processor 102 does not have to go through the interconnecting bus 106 and wait for the bus 106 traffic, the processor 102 can generally access data in its cache 108 faster than it can access data in the main memory 104. In a normal operation, a processor 102N first reads data from memory 104 and copies that data to the processor's own cache 108N. During subsequent accesses for the same data the processor 102N fetches the data from its own cache 108N. In effect, after the first read, data in cache 108N is the same copy of data in memory 104 except that the data is now in a high-speed local storage. Typically, cache 108N can be accessed in one or two cycles of CPU time while it takes a processor 102 15 to 50 cycles to access memory 104. A typical processor 102 runs at about 333 Mhz or 3 ns (nanoseconds) per cycle, but it takes at least 60 ns or 20 cycles to access memory 104.
A measure of data, typically 32, 64, 128, or 2.sup.n bytes, brought from memory 104 to cache 108 is usually called a "cache line." The data of which a copy was brought to cache 108 and which remains in memory 104 is called a "memory line." The size of a cache line or a memory line is determined by a balance of the overhead per read/write operation versus the usual amount of data transferred from memory and cache. An efficient size for a cache line results in transfers spending about 25% of their time on overhead and 75% of their time on actual data transfer.
A particular problem with using caches is that data becomes "stale." A first processor 102A may access data in the main memory 104 and copy the data into its cache 108A. If the first processor 102A then modifies the cache line of data in its cache 108A, then at that instant the corresponding memory line becomes stale. If a second processor, 102B for example, subsequently accesses the original data in the main memory 104, the second processor 102B will not find the most current version of the data because the most current version is in the cache 108A. For each cache-line address, cache coherence guarantees that only one copy of data in cache 108 can be modified. Identical copies of a cache line may be present in multiple caches 108, and thus be read by multiple processors 102 at the same time, but only one processor 102 is allowed to write, i.e., modify, the data. After a processor 102 writes to its cache 108 that processor 102 must "invalidate" any copies of that data in other caches to notify other processors 102 that their cache lines are no longer current.
FIG. 2A shows valid cache lines D0 for caches 108A to 108N whereas FIG. 2B shows cache 108B with an updated cache line D1 and other caches 108A, 108C, and 108N with invalidated cache lines D0. The processors 102A, 102C, and 102N with invalidated cache data D0 in their respective caches 108 must fetch the updated version of cache line D1 if they want to access that data line again.
Nonnally and for illustrative purposes in the following discussion, cache coherence protocols are executed by processors 102 associated with their related caches. However, in other embodiments these protocols may be executed by one or more specialized and dedicated cache controllers.
There are different cache coherence management methods for permitting a processor 102 to modify its cache line in cache 108 and invalidate other cache lines. One method (related to the present invention) utilizes, for each cache line, a respective "shared list" representing cache-line correspondences by "double-links" where each cache has a forward pointer pointing to the next cache entry in the list and a backward pointer pointing to the previous cache entry in the list. Memory 104 has a pointer which always points to the head of the list.
FIG. 3 shows a linked list 300 of caches 108A . . . 108N with the associated memory 104. Memory 104 has a pointer which always points to the head (cache 108A) of the list while the forward pointers Af, Bf, and Cf of caches 108A, 108B, and 108C respectively point forward to the succeeding caches 108B, 108C, and 108D (not shown). Similarly, backward pointers Nb, Cb, and Bb of caches 108N, 108C, and 108B respectively point backward to the preceding caches. Because each cache unit 108 is associated with a respective processor 102, a linked list representation of cache 108 is also understood as a linked list representation of processors 102.
There are typically two types of cache sharing lists. The first type of list is the read-only (sometimes called "fresh") list of caches for which none of the processors 102 has permission to modify the data. The second type of list is a read-write (sometimes called "owned") list of caches for which the head-of-list processor 102 may have permission to write to its cache 108. A list is considered "stable" after an entry has been completely entered into or completely deleted from the list. Each of the stable list states is defined by the state of the memory and the states of the entries in the shared list. Relevant states of memory include HOME, FRESH, and STALE. HOME indicates no shared list exists, FRESH indicates a read-only shared list, and STALE indicates the shared list is a read-write list and data in the list can be modified. A processor 102 must get authorization to write to or read from memory. A list entry always enters the list as the list head, and the action of entering is referred to as "prepending" to the list. If a list is FRESH (the data is the same as in memory), the entry that becomes the newly created head receives data from memory; otherwise it receives data from the previous list head. In a read-write list, only the head is allowed to modify (or write to) its own cache line and, after the head has written the data, the head must invalidate the other stale copies of the shared list. In one embodiment, invalidation is done by purging the pending invalidated entries of the shared list.
FIGS. 4A-4F illustrate how the two types of lists are created and grown. Each of the FIGS. 4 includes a before and an after list with states of the list and memory 104. In FIG. 4A, initially memory 104 is in the HOME state, indicating there is no cache shared list. Processor 102A requests permission to read a cache line. Since this is a read request, memory 104 changes from the HOME state to the FRESH state, and the resulting after list 402AR is a read-only list with one entry 108A. Cache 108A receives data from memory 104 because cache 108A accesses data that was previously uncached. This starts the read-only list 402AR.
In FIG. 4B processor 102B requests a read permission to enter the read-only list 402B, which is the same list as 402AR of FIG. 4A. Cache 108B then becomes the head of the list 402BR receiving data line from head 108A. The list 402BR is still a read-only list since both entries of the list have asked for read-only permission, and therefore the memory state remains FRESH.
In FIG. 4C, memory 104 is initially in the HOME state and processor 102A requests a read-write permission. Cache 108A then becomes the head of the list 402CR. Because a read-write permission was requested, list 402CR is a read-write list. As soon as memory 104 grants a read-write permission, memory 104 changes from the HOME state to the STALE state.
In FIG. 4D processor 102B requests a read permission to enter a read-write list 402D. Cache 108B becomes the head of the list 402DR. Since memory 104 is initially in the STALE state, the resulting list 402DR is a read-write list and memory 104 remains in the STALE state.
In FIG. 4E, the initial list 402E is read-only with memory 104 in the FRESH state, and processor 102B requests a write permission. Cache 108B then becomes the head of the list 402ER. Since processor 102B asked for a write permission, memory 104 changes state from FRESH to STALE, and list 402ER is a read-write list.
In FIG. 4F the list 402F is a read-write list and processor 102B requests a write permission. Since list 402F is read-write, list 402FR is also read-write, and memory 104 remains in the STALE state.
Cache list entries may be deleted. However, deleting a head-of-list presents a problem in mixed-coherence protocols, which exist where processor 102 associated with the head of the list supports a read-only option while processor 102 associated with the next-list entry supports only a read-write option. Currently most multi-processor systems support read-write lists and read-only lists are optional.
FIG. 5 illustrates how a cache head 108D would be deleted if processor 102C supports a read-only list. Initially, the list 502A is read-only and memory 104 is FRESH. After cache 108D has been deleted, cache 108C becomes the head of the list 502R, possessing all read-only characteristics of cache 108D and memory 104. List 502R would be read-only with memory 104 in the FRESH state. However, if processor 102C does not support a read-only list, cache 108C cannot inherit the read-only property from memory 104 and cache 108D, resulting in a conflicting situation.
Prior art attempts to resolve this conflict are illustrated in the flowchart of in FIG. 6. In step 600, the head of the list informs the next-list entry that the next-list entry is about to become a read-only-list head. In step 604 the next-list entry responds that it cannot become a read-only-list head because its system does not support the read-only-list option. In step 608 the head of the list then invalidates all copies in the list and in step 612 returns them to memory. However, this solution is inefficient because even processor 102 of the head list wants to withdraw its cache 108 from the list, but other processors may still want to access the same cache copies. In such a situation the other processors must re-start a new sharing cache list by getting the desired cache line from memory 104.
The IEEE Standard of Scalable Coherent Interfaces, IEEE Std. 1596-1992, Institute of Electrical and Electronics Engineers, Aug. 2, 1993, defines mechanism for deleting a read-only entry. This mechanism first detects a conflict, converts the list from the read-only to the read-write state and then allows deletion of the head of the list. However, the deleting protocols rely on detection of conflicts and are complex because the conversion between read-only and read-write states is a special operation and, due to other conflicts, is not always successful.